package codeRandomThoughts.Test416分割等和子集;

public class Solution2 {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) return false;
        //转换成01背包问题,看背包里是否能正好装价值为(sum/2)的物品
        int targetSum = sum / 2;
        int[][] dp = new int[nums.length][targetSum + 1];

        //初始化
        //j=0 都为0
        //i=0
        for (int j = nums[0]; j <= targetSum; j++) {
            dp[0][j] = nums[0];
        }

        for (int i = 1; i < nums.length; i++) {
            for (int j = 1; j <= targetSum; j++) {
                if (j < nums[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
                }
                if (dp[i][j] == targetSum) return true;
            }
        }

        return false;
    }
}
